/*
 * @Author: szx
 * @Date: 2022-03-09 13:26:30
 * @LastEditTime: 2022-03-09 14:45:26
 * @Description:
 * @FilePath: \leetcode\700-799\743\743.js
 */
/**
 * @param {number[][]} times
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var networkDelayTime = function (times, n, k) {
    const INF = Number.MAX_SAFE_INTEGER;
    const g = new Array(n).fill(INF).map(() => new Array(n).fill(INF));
    for (let t of times) g[t[0] - 1][t[1] - 1] = t[2];
    // 从第k个节点（源点）到第i个节点的的距离
    const dist = Array.from(g[k - 1]);
    dist[k - 1] = 0;
    // 节点是否被用过的
    const used = new Array(n).fill(false);
    //共有n轮，每轮确定一个节点
    for (let i = 0; i < n; i++) {
        let pos = -1;
        let min = INF;
        // 找到该轮中未确定且距离k节点最小的节点位置pos
        for (let j = 0; j < n; j++) {
            if (!used[j] && dist[j] < min) {
                pos = j;
                min = dist[j];
            }
        }
        if (pos == -1) break;
        used[pos] = true;
        for (let j = 0; j < n; j++) {
            if (!used[j]) {
                dist[j] = Math.min(dist[j], dist[pos] + g[pos][j]);
            }
        }
    }
    let ans = Math.max(...dist);
    return ans == INF ? -1 : ans;
};
